#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

输入: "cbbd"
输出: "bb"
*/

#define MAX_NUM 1000

/* g[i][j]表示i到j之间的字符串是否为回文数 */
int g_data[MAX_NUM + 1][MAX_NUM + 1] = { 0 };

char* longestPalindrome(char* s)
{
    if (*s == '\0') {
        return s;
    }
    
    memset(g_data, 0, (MAX_NUM + 1) * (MAX_NUM + 1) * sizeof(int));
    
    int len = strlen(s);
    for (int i = 0; i < len; i++) {
        g_data[i][i] = 1;
    }

    int max = 1;
    int start = 0;
    for (int i = len - 2; i >= 0; i--) {
        for (int j = i + 1; j < len; j++) {
            if (s[i] == s[j] && (g_data[i + 1][j - 1] || i + 1 == j)) {
                g_data[i][j] = 1;
                if (max < j - i + 1) {
                    max = j - i + 1;
                    start = i;
                }
            }
        }
    }

    char* result = s + start;
    result[max] = '\0';
    return result;
}

int main(int argc, char* argv[])
{
    char test[] = "babad";
    char* str = longestPalindrome(test);
    // char *str = longestPalindrome("cbbd");
    printf("%s\n", str);
    return 0;
}